package 二叉树;

import java.util.LinkedList;
import java.util.Queue;

public class _662_二叉树最大宽度 {
	public int widthOfBinaryTree(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int size = 1;
		root.val = 1;
		int diff = 0;
		TreeNode firNode = null;
		TreeNode lastNode = null;
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);
		while (!queue.isEmpty()) {
			boolean isFirst = true;
			while (size != 0) {
				size--;
				TreeNode node = queue.poll();
				if (isFirst) {
					firNode = node;
					isFirst = false;
				}
				if (size == 0) {
					lastNode = node;
				}
				if (node.left != null) {
					node.left.val = node.val * 2;
					queue.add(node.left);
				}
				if (node.right != null) {
					node.right.val = node.val * 2 + 1;
					queue.add(node.right);
				}
			}

			size = queue.size();
			diff = Math.max(diff, lastNode.val - firNode.val + 1);
		}
		return diff;

	}
}
